Large-scale data processing systems typically utilize a tremendous amount of memory. This is particularly true in multiprocessing systems where multiple processing units are implemented. There are several memory methodologies known in the art that provide for efficient use of memory in such multiprocessing environments. One such memory methodology is a distributed memory where each processor has access to its own dedicated memory, and access to another processor's memory involves sending messages via an inter-processor network. While distributed memory structures avoid problems of contention for memory and can be implemented relatively inexpensively, it is usually slower than other memory methodologies, such as shared memory systems.
Shared memory is used in a parallel or multiprocessing system, and can be accessed by more than one processor. The shared memory is connected to the multiple processing units--typically accomplished using a shared bus or network. Large-scale shared memories may be designed to cooperate with local cache memories associated with each processor in the system. Cache coherency protocols ensure that one processor's cached copy of a shared memory location is invalidated when another processor writes to that location.
In order to initiate and establish transfers of data in such a system, a device desiring a data transfer issues a data transfer request. For example, a data transfer request may be issued by a processor to the main memory to fetch a data segment from the main memory, which is thereafter supplied by the main memory to the processor's local memory or cache memory. It is possible that any of the processors, input/output devices and memory devices may be the source or the destination of a data transfer. Managing the data transfer requests in a system where there may be multiple request sources and multiple request destinations therefore becomes very important. Conservatively managing the transfer of these requests may lead to a reduction in system throughput, while mismanagement to obtain greater throughput may lead to memory access conflicts.
For example, where the number of request sources is unequal to the number of request destinations, it is possible that each of the request sources has issued an active data transfer request. Where the number of destinations is less than the number of active data transfer requests, this implies that some of the destinations are being targeted by multiple data transfer requests. A manner of fairly distributing these data transfer requests is required.
Further, because such a system may include multiple destinations for the data transfer requests, such as multiple memory blocks or other local memories, it is possible that a particular request source may issue multiple data transfer requests each identifying a different destination for the request. If these data transfer requests are allowed to be issued simultaneously to the request destination, such as a single-port memory device, indeterminate results can occur. It is therefore important to properly manage the flow of the data transfer requests, taking into account the manner in which the data targeted by the data transfer request is to be routed from the data source to the data destination.
Finally, while managing the flow of data transfer requests, it is also important to maximize system data throughput. To do so requires maximizing the throughput of the data transfer requests. To allow only one data transfer request to be issued at a time would severely limit the system's throughput where data transfer requests between multiple sources and destinations are pending.
Therefore, it would be desirable to provide a system and method that maximizes data throughput, while properly and fairly managing concurrently-pending data transfer requests. The present invention provides a multi-level queuing architecture to manage the data transfer requests, while allowing data transfers to occur in parallel in accordance with rules established by the multi-level queuing architecture. The present invention offers these and other advantages over the prior art, and provides a solution to the shortcomings of the prior art.